Coding Challenge for High School Students

One of the goals of the Nowhere Developers Conference is to bring, develop, and retain technical talent in the region. That starts with getting kids introduced to and interested in programming at a younger age. Nowhere Developers is proud to offer ten scholarship tickets to high school students to attend the conference on March 15, 2018. The students will be selected based on their code submissions to a coding challenge described below. The deadline is March 1st. The winners will be notified on March 5th.

If you have any questions or feedback, feel free to reach out to Kanat Bekt at kanat@supplypike.com.

 

Instructions

There are two parts to the challenge, second part being optional. We encourage you to give a try to both parts!

  1. Read through the problem description below.
  2. Write a program to solve it in the programming language you're most comfortable with.
  3. Email the following information to challenge@nowheredevelopers.com:
    • Subject line: challenge-2018
    • Attach three files bundled in a ZIP or tar format.
      • Separate single files for each part of the challenge (e.g part1.py, part2.py, PartOne.java, PartTwo.java).
      • readme.txt file with a short information about you, your interests, how you got into programming, and something awesome you've built. Keep it under 350 words.
    • You may include any comment or feedback in the email body.

Here are some things to keep in mind.

  • Your program should receive input from standard input (stdin) and produce output on standard output (stdout).
  • Your program will be executed against a suite of test cases we have pre-prepared. You might want to test your code against various edge cases before submitting.
  • Runtime speed is important, so bonus points for a fast solution. Speed is relative to the programming language you choose.
  • Stick to good programming practices and conventions. Somebody will read your code on our end!
  • No cheating or collaboration. We will detect duplicate or similar submissions.
  • Have fun and learn something new while doing the challenge!


Part One: No Friends

Two numbers are assumed to be friends if they are seen in a pair together. For example, for integers 1 to 10, we have the following friend pairs (1 8), (8 3), (2 7). The values that are not friends are 4, 5, 6, 9, and 10.

Given a positive integer n and a set of friend pairs, decide those values from 1 to n that do not have any friends. You may assume that an integer cannot be a friend of itself.

Input

Each test case has several lines. The first line contains a positive integer n where 1 ≤ n ≤ 10,000. The rest of the lines contains two integers separated by a space.

There is a blank line after every test case. Input will contain multiple test cases.

Output

For each test case, output a single line followed by a blank line. The line must contain those integers, in an increasing order separated by a space, that do not have any friends. Output NONE if all have at least one friend.

Example

Input

.
    10
    1 8
    8 3
    2 7

    8
    1 8
    8 3
    2 7

    4
    1 4
    3 2
    3 4

.

Output

.
    4 5 6 9 10

    4 5 6

    NONE
.


Part Two: All Friends (Bonus)

The previous part identifies all the values that do not have any friends. In this part, we list integers by groups where all values that are friends of the same integer belong to the same group.

Input

Each test case has several lines. The first line contains a positive integer n where 1 ≤ n ≤ 10,000. The rest of the lines contains two integers separated by a space.

There is a blank line after every test case. Input will contain multiple test cases.

Output

For each test case, output several lines: each line containing those integers, in an increasing order separated by a space, that are friends of each other. The first element of each line are sorted increasingly. Output NONE if no friend exists. There is a blank line to end the output.

Example

Input

.
    10
    1 8
    8 3
    2 7

    8
    1 8
    8 3
    2 7
    7 8

    8

.

Output

.
    1 3 8
    2 7

    1 2 3 7 8

    NONE

.


Source

This problem is taken from a past Arkansas High School Programming Competition (HSPC) problem set. The competition is held anuually at the University of Arkansas, Fayetteville. A few SupplyPike engineers are heavily involved with the organization of the event. If you're interested in participating or learning more about HSPC, please visit their website at hspc.uark.edu.