Scholarship Challenge Nowhere Developers

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 julian@sankergroup.org:

Here are some things to keep in mind.


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

There can be any number of test cases, each of which has several (2 or more) lines. The first line contains a positive integer n where 1 ≤ n ≤ 10,000. The rest of the lines each contain 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