สวนสัตว์วงกลม (Great Circular Zoo) เป็นความภาคภูมิใจล่าสุดของหมู่ชนภาคพื้นเอเชีย แปซิฟิก สวนสัตว์แห่งนี้ตั้งอยู่บนเกาะเล็กๆแห่งหนึ่งในมหาสมุทรแปซิฟิก บนเกาะนี้ประกอบด้วย กรงสัตว์ต่างๆวางเป็นวงกลม โดยแต่ละกรงจะมีสัตว์หาดูได้ยากที่แตกต่างกัน

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

ตัวอย่างเช่น ให้พิจารณารายการของเด็กและสัตว์ที่แสดงดังต่อไปนี้

เด็ก ||||||||||||||||||||| กรงที่มองเห็นได้ ||||||| สัตว์ที่กลัว |||||||| สัตว์ที่ชอบ

อเล็กซ์ (Alex) ||||||||||| 2, 3, 4, 5, 6 ||||||| กรง 4 |||||||||| กรง 2, 6

พอลลี่ (Polly) ||||||||||| 3, 4, 5, 6, 7 ||||||| กรง 6 |||||||||| กรง 4

ชัยธัญญา (Chaitanya) ||| 6, 7, 8, 9, 10 |||||| กรง 9 |||||||||| กรง 6, 8

หวาน (Hwan) ||||||| 8, 9, 10, 11, 12 ||||||| กรง 9 |||||||||| กรง 12

กาชู (Ka-Shu) ||||||| 12, 13, 14, 1, 2 ||||||| กรง 12, 13, 2 |||| —

==========================================

สมมติว่า คุณนำสัตว์จากกรงที่ ๔ และ ๑๒ ออก นั่นจะทำให้ อเล็กซ์และกาชูมีความสุข เพราะว่ามี สัตว์อย่างน้อยหนึ่งตัวที่เด็กทั้งสองคนกลัวได้ถูกนำออกไปจากกรง นอกจากนี้ ชัยธัญญาก็ยังมี ความสุขเพราะว่ากรงที่ ๖ และ ๘ ก็ยังมีสัตว์ที่ตนชอบอยู่ อย่างไรก็ตาม ทั้งพอลลี่และหวานก็คง จะไม่มีความสุขเนื่องจากไม่เห็นชนิดสัตว์ที่ตัวเองชอบแล้วยังเห็นแต่ชนิดที่ทั้งสองคนกลัว สรุปก็ คือการนำสัตว์ออกจากกรงตามตัวอย่างนี้ทำให้เด็กมีความสุข ๓ คน

ลองดูใหม่เอาสัตว์เข้าไปในกรงใหม่ แล้วสมมุติว่าคุณเอาสัตว์ออกจากกรงที่ ๔ และ ๖ แทน อเล็กซ์ และพอลลี่จะมีความสุขเพราะว่าสัตว์ที่กลัวในกรงที่ ๔ และ ๖ ได้ถูกเอาออกไปแล้ว ชัยธัญญาก็มี ความสุขด้วยเนื่องจากแม้ว่าสัตว์ในกรงที่ ๖ ถูกเอาออกไป เขาก็ยังเห็นสัตว์ที่เขารักในกรงที่ ๘ ทำนองเดียวกัน หวานก็มีความสุขเพราะว่าเธอเห็นเฉพาะสัตว์ในกรงที่ ๑๒ ซึ่งเป็นสัตว์ที่เธอชอบ ในกรณีนี้คนที่ไม่มีความสุขมีคนเดียวคือ กาชู สุดท้าย สมมติว่าคุณเอาสัตว์ทั้งหมดกลับเข้าไปในกรงอีกครั้งและเอาสัตว์ออกจากกรงที่ ๑๓ คราวนี้กาชูจะมีความสุขเพราะว่าสัตว์ที่เขาไม่กลัวหนึ่งตัวได้ถูกเอาออกไปจากกรง ส่วนอเล็กซ์ พอลลี่ ชัยธัญญา และ หวาน ก็มีความสุขเหมือนกันเนื่องจากว่าสามารถมองเห็นสัตว์ที่ตัวเองชอบ ได้อย่างน้อยหนึ่งตัว ดังนั้นวิธีการนี้เป็นวิธีที่ทำให้มีจำนวนเด็กมีความสุขมากที่สุดนั่นคือ ทั้งห้าคน มีความสุข

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัว N C โดยที่ N คือจำนวนของกรงสัตว์ (1 ≤N≤10 000) และ C เป็นจำนวนของนักเรียน (1≤C≤50 000) หมายเลขกรงจะนับตามเข็มนาฬิกาจาก 1,2,…,N ต่อจากนั้น C บรรทัดจะเป็นรายละเอียดของเด็กแต่ละคน โดยมีรูปแบบคือ E F L X1 X2 … XF Y1 Y2 … YL

โดยที่

E คือ หมายเลขกรงแรกที่เด็กมองเห็น (1≤E≤N) หรืออาจกล่าวได้ว่า เด็กสามารถ มองเห็นกรงหมายเลข E, E+1, E+2, E+3, และ E+4 สังเกตว่าหมายเลขของกรงที่มีค่า มากกว่า N จะถูกแปลงกลับให้เป็นหมายเลขของกรงตามวงกลม เช่น ถ้า N=14 และ

E=13 เด็กจะเห็นกรงหมายเลข 13 14 1 2 และ 3

F คือจำนวนของสัตว์ที่เด็กกลัว และ L คือจำนวนของสัตว์ที่เด็กชอบ

X1… XF เก็บหมายเลขของสัตว์ที่เด็กกลัว (1 ≤ X1,…,XF ≤ N).

Y1…YL เก็บหมายเลขสัตว์ที่เด็กชอบ (1 ≤ Y1,…,YL ≤ N)

X1…XF, Y1…YL เป็นหมายเลขกรงที่เด็กจะมองเห็นได้ ซึ่งค่าเหล่านี้จะมีค่าที่ไม่ซ้ำกัน 10

เด็กแต่ละคนจะถูกจัดลำดับเรียงตามค่า E (ซึ่งนั่นก็คือ ข้อมูลเด็กคนที่มีค่า E ต่ำที่สุดจะแสดงให้ เห็นก่อนและข้อมูลของเด็กที่มีค่า E สูงสุดจะเป็นข้อมูลชุดสุดท้าย) สังเกตว่า อาจมีเด็กมากกว่า หนึ่งคนที่จะมีหมายเลขกรงแรก (E) เหมือนกัน

ข้อมูลส่งออก

มีจำนวนเต็มหนึ่งตัว เป็นค่าที่เป็นจำนวนเด็กที่มีความสุขที่มากที่สุด

ข้อมูลตัวอย่าง ๑ ข้อมูลนำเข้า 14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2 ข้อมูลส่งออก 5

ข้อมูลตัวอย่าง ๒ ข้อมูลนำเข้า 12 7 1 1 1 1 5 5 1 1 5 7 5 0 3 5 7 9 7 1 1 7 9 9 1 1 9 11 9 3 0 9 11 1 11 1 1 11 1 ข้อมูลส่งออก 6

คำอธิบาย

ข้อมูลตัวอย่าง ๑ แสดงตามตัวอย่างที่อธิบายข้างต้นซึ่งสามารถทำให้เด็กทุกคน (C = 5) มี ความสุขได้ และในข้อมูลตัวอย่าง ๒ แสดงตัวอย่างที่ไม่สามารถทำให้เด็กทุกคนมีความสุขได้ (C = 7)

คำถาม

ให้เขียนโปรแกรมทำการ input ค่าที่จะให้ หาค่า output ต่อไปนี้

File name : zoo.in

10 10

1 1 1 3 2

2 1 0 4

3 1 1 5 6

4 1 1 7 6

5 1 0 6

6 1 2 9 8 10

7 1 0 10

8 1 0 8

9 1 1 1 2

10 1 0 2

End Line File : zoo.in

nikom2532@hotmail.com : ผู้ post