พูดคุย:CERC12

Graphic Madness (Problem K)

มีการ์ดจออยู่สองยี่ห้อซึ่งมีโครงสร้างของแผงวงจรคล้ายกัน โดยแต่ละการ์ดนั้นจะประกอบด้วย ปม และ เส้นเชื่อมระหว่างปม ปมนั้นมีอยู่สองประเภทคือ ปมแบบ processor และปมแบบ socket โดยที่มีกฎของการเชื่อมต่อดังนี้อ

• ปมแบบ socket นั้นจะมีเส้นเชื่อมเส้นเดียวเชื่อมไปยังปมที่เป็นปม processor เท่านั้น
• ปม processor นั้นจะต้องเชื่อมต่อกับปมอื่น ๆ อย่างน้อยสองปม
• สำหรับปมสองปมใด ๆ จะมี path เชื่อระหว่างปมทั้่งสองปมนี้เพียง path เดียว กล่าวคือ graph ของปมและเส้นเชื่อมนี้จะเป็นต้นไม้เสมอ

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

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

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

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็มสามตัว k,n,m (2 <= k <= 1 000; 1 <= n,m <= 1 000) ซั่งระบุถึงจำนวนของ socket, จำนวนของ processor ในการ์ดแรก, จำนวนของ processor ในการ์ดสอง ตามลำดับ เรากำหนดให้ปมต่าง ๆ ของการ์ดทั้ง 2 มีสัญลักษณ์ดังต่อไปนี้
  • AS1, AS2, ..., ASk คือปม socket ของการ์ดแรก
  • AP1, AP2, ..., APn คือปม processor ของการ์ดแรก
  • BS1, BS2, ..., BSk คือปม socket ของการ์ดสอง
  • BP1, BP2, ..., BPm คือปม processor ของการ์ดสอง
• หลังจากนั้นอีก n - k + 1 บรรทัดจะเป็นการอธิบายการเชื่อมต่อของการ์ดแรก โดยที่แต่ละบรรทัดจะประกอบด้วยชื่อมของการ์ดใบแรกสองปม ซึ่งระบุว่ามีเส้นเชื่อมระหว่างปมทั้งสอง
• หลังจากนั้นจะคั่นด้วยบรรทัดว่างหนึ่งบรรทัด
• หลังจากนั้นอีก m - k + 1 บรรทัดจะเป็นการอธิบายการเชื่อมต่อของการ์ดสองในรูปแบบเดียวกัน
• หลังจากนั้นจะคั่นด้วยบรรทัดว่างหนึ่งบรรทัด
• k บรรทัดสุดท้ายอธิบายถึงสายสัญญาณที่เชื่อมต่อระหว่างการ์ด โดยที่แต่ละบรรทัดจะมีชื่อปม socket อยู่สองปม โดยทั้งสองปมเป็นของการ์ดคนละตัว และปม socket แต่ละปมนั้นจะปรากฎเพียงครั้งเดียว
• จะมีบรรทัดว่างตามท้ายอีกหนึ่งบรรทัด ยกเว้นข้อมูลทดสอบชุดสุดท้าย