9754번 - ระบายสีต้นไม้ (Tree Coloring) 다국어

ตน้ ไมค้ือกราฟแบบไม่มีทิศทางที่เชื่อมต่อกนั (connected) และไม่มีวงรอบ (cycle) ให้ต้นไม้ที่มีN โหนด และเส้นเชื่อม N-1 เส้น เราต้องการจะ ระบายสีต้นไม้กล่าวคือเราตอ้งการกา หนดสีให้กบัโหนดต่าง ๆ โดยสีเป็ นจ านวนเต็มจากเซต {1,2,...,K} โดยที่รับประกนัวา่ โหนดที่มีเส้นเชื่อมติดกนั จะมีสีไม่ซ้า กน

ให้คุณเขียนโปรแกรมเพื่อคา นวณว่าสามารถทา ไดก้ี่แบบ เนื่องจากค าตอบสามารถมีได้จ านวนมาก ให้ตอบจ านวนวิธีmodulo 93563

บรรทัดแรก ระบุจ านวนเต็ม T (1 ≤ T ≤ 10) แทนจ านวนข้อมูลชุดทดสอบ จากน้นัจะมีขอ้มูลชุดทดสอบ T ชุด ในรูปแบบดงัน้ี

• บรรทัดแรกของข้อมูลชุดทดสอบระบุจ านวนเต็มสองจ านวน N และ K โดยที่ N แทนจ านวนโหนด (2 ≤ N ≤ 200) และ K แทน จ านวนสีที่สามารถใช้ได้(1 ≤ K ≤ 10) โหนดจะมีหมายเลขต้งัแต่ 1 ถึง N
• อีก N-1 บรรทัด ระบุข้อมูลของเส้นเชื่อมในต้นไม้แต่ละบรรทดัระบุจา นวนเตม็ สองจา นวน A และ B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) ระบุวา่ มีเส้นเชื่อมระหวา่ งโหนดหมายเลข A และ B

มีท้งัสิ้น T บรรทัด สา หรับขอ้มูลนา เขา้แต่ละชุดให้พิมพจ์า นวนวิธีการระบายสีmodulo 93563 เรียงตามล าดับ บรรทดัและหน่ึงค่า