1085 : ล่าสมบัติทั่วทุกทิศ (explore)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

          ในที่สุด หลังจากลุ้นตัวโก่ง คุณก็สามารถผ่านการตอบปัญหาไปได้ ขั้นต่อมาก็คือ ตามหาอัญมณีนี้ในโบราณสถานอันกว้างใหญ่
         
          คุณรู้มาว่า อัญมณีชิ้นนี้ถูกซ่อนอยู่ในโบราณสถานซึ่งมีลักษณะเป็นห้องๆซึ่งมีทั้งหมด n ห้อง คือห้องที่ 1,2,3,…,n ซึ่งห้องที่อยู่ติดกันจะมีประตูหากันได้ กล่าวคือ ห้องที่ 1 จะมีประตูเชื่อมกับห้องที่ 2 , ห้องที่ 2 จะมีประตูเชื่อมกับห้องที่ 3 , … , ห้องที่ n-1 จะมีประตูเชื่อมกับห้องที่ n

          ***โดยประตูนั้นจะเป็นประตูทางเดียว กล่าวคือ จะไม่สามารถใช้เดินทางจากห้อง i+1 ไปยัง ห้อง i ได้ แต่จะสามารถใช้เดินทางได้เฉพาะการเดินทางจาก ห้อง i ไปยัง ห้อง i+1 (เมื่อ 1 <= i < n)

          เนื่องจากอัญมณีดังกล่าวนั้นมีมูลค่าสูงจนประเมินไม่ได้ มันจึงถูกซ่อนอยู่ในห้องที่ n ยิ่งไปกว่านั้นแล้ว เทพเจ้าที่รักษาสถานที่นี้ไม่ต้องการให้คุณได้อัญมณีล้ำค่าไปง่ายๆจึงสร้างหินมากั้นห้องบางห้องไว้ทำให้คุณไม่สามารถเดินไปต่อยังห้องต่อไปได้

          แต่ยังโชคดีที่คุณค้นพบระบบขนย้ายมวลสารในโบราณสถานนี้ กล่าวคือคุณสามารถข้ามจากห้องที่มีเครื่องขนย้ายมวลสารไปยังห้องปลายทางที่เครื่องกำหนดได้ ซึ่งเครื่องนี้มีลักษณะพิเศษคือ จะเคลื่อนย้ายคุณไปยังห้องที่มีเลขสูงกว่าเท่านั้น คุณจะได้รับข้อมูลของโบราณสถานทั้งหมดแล้วจงหาว่า คุณสามารถไปถึงห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด โดยเริ่มต้นคุณอยู่ที่ห้องหมายเลข 1

งานของคุณ
          จงเขียนโปรแกรมรับข้อมูลของโบราณสถานนี้ และตอบว่า คุณสามารถไปยังห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด

ข้อมูลนำเข้า
          บรรทัดแรก มีจำนวนเต็มบวก n, m, k แทนจำนวนห้องทั้งหมด จำนวนเครื่องขนย้ายมวลสาร และ จำนวนหินกั้นทางตามลำดับ โดยที่ 1 <= n <= 500,000, 0 <= m <=1,000,000, 0 <= k <= n-1

          อีก m บรรทัดต่อมา แต่ละบรรทัดประกอบด้วยจำนวนเต็ม 2 จำนวน a, b หมายความว่า ในห้อง a  มีเครื่องขนย้ายมวลสาร ที่สามารถใช้เดินทางไปยังห้อง b ได้

          อีก k  บรรทัดต่อมา แต่ละบรรทัดมีจำนวนเต็ม x ซึ่งบอกว่ามีหินกั้น ระหว่างห้อง x กับ x + 1

ข้อมูลส่งออก
          มีบรรทัดเดียว ถ้าสามารถเก็บอัญมณีได้ให้พิมพ์ 1 ถ้าเก็บอัญมณีไม่ได้ให้พิมพ์ 0 แล้วตามด้วยหมายเลขห้องที่มีค่าสูงสุดที่ไปถึงได้

โจทย์โดย: วีระกานต์ สินทวีเลิศมงคล
ที่มา: TOI.CPP:03-2009

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
5 1 1  2 5 2	1
5 1 1 1 2 2	0 2

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้