Judge's Lantern

# Judge's Lantern ## Problem A wise cow named Bessie is placing magical lanterns in the MOOSACO arena to guide judges through the competition. She has N pillars arranged in a line where she can place lanterns. She needs to place exactly K lanterns on distinct pillars. However, some pairs of pillars cannot both have lanterns due to ancient rules—if a certain pair is forbidden, you cannot light both pillars in that pair simultaneously. Your task is to output any valid placement of K lanterns among the N pillars that respects all forbidden pairs. Because multiple valid placements may exist, we use a custom checker to validate any correct solution. ## Input - **Line 1:** N K (number of pillars, number of lanterns to place) - **Line 2:** F (number of forbidden pairs) - **Lines 3 to F+2:** Each line contains two integers u v, representing a forbidden pair ## Output Output exactly K distinct pillar indices (1-indexed) on which to place lanterns. You may output them in any order. ## Constraints - 1 ≤ K ≤ N ≤ 100 - 0 ≤ F ≤ N(N-1)/2 - 1 ≤ u, v ≤ N, u ≠ v - Output indices must be distinct and in range [1, N] - Your output must not contain both indices from any forbidden pair ## Sample Input ``` 5 2 1 2 4 ``` ## Sample Output ``` 1 5 ``` ## Sample Explanation We have 5 pillars and must place 2 lanterns. The only forbidden pair is (2, 4), meaning we cannot place lanterns on both pillar 2 and pillar 4 simultaneously. One valid solution is to place lanterns on pillars 1 and 5. This avoids the forbidden pair (2, 4), so it is a valid answer. Other valid answers include (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5). ## Checker This problem uses a **custom checker** because multiple valid outputs are acceptable. Any placement of K lanterns that avoids all forbidden pairs is correct. The judge will use a checker program to verify that your output: 1. Contains exactly K distinct pillar indices 2. All indices are in the range [1, N] 3. No forbidden pair exists entirely within your output