2002 : Zoo
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 16 megabyte(s)
สวนสัตว์วงกลม (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 เป็นหมายเลขกรงที่เด็กจะมองเห็นได้ ซึ่งค่าเหล่านี้จะมีค่าที่ไม่ซ้ำกัน
เด็กแต่ละคนจะถูกจัดลำดับเรียงตามค่า E (ซึ่งนั่นก็คือ ข้อมูลเด็กคนที่มีค่า E ต่ำที่สุดจะแสดงให้เห็นก่อนและข้อมูลของเด็กที่มีค่า E สูงสุดจะเป็นข้อมูลชุดสุดท้าย) สังเกตว่า อาจมีเด็กมากกว่าหนึ่งคนที่จะมีหมายเลขกรงแรก (E) เหมือนกัน

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

ที่มา: Asia-Pacific Informatics Olympiad

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
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

ความช่วยเหลือ: Hint[1]  

กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (4 บอท)