Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Friendship Database

Limits 1s, 512 MB

You have created a new social media for testing the irrationality of human behavior. In order to conduct some experiments, you have invited N person to join your site. These N people are completely unknown to each other and you want to figure out how some unknown people interacts with one another. You have given each individual an unique identification number from 1 to **N&&. Whenever two person communicates within your social media, you want to know whether this interaction is a completely new one, or it has happened before.

Now your job is to create a database that would store all the interaction history and report new ones. You can safely assume that when person i and j interacts, they do it mutually. That is, whenever i speaks with j, j talks back to i.

Input

The first line contains two integers N ( 1 ≤ N ≤ 1000 ) and M ( 1 ≤ M ≤ 100000 ), the number of people in your social media and the number of interactions between them respectively.

The following M lines will contains two integers Ai and Bi ( 1 ≤ Ai, Bi, ≤ N , Ai != Bi ) each, indicating that there’s an interaction between person Ai and Bi.

Output

For each line of interactions, print new if this interaction happened for the first time or old if that interaction has happened before.

Sample

InputOutput
5 5
1 2
2 3
1 3
2 3
3 1
new
new
new
old
old

Discussion

Statistics


91% Solution Ratio

oneoff.ZQa4IH1LSeEarliest, Nov '16

SIR.24Fastest, 0.0s

fahimChy_IIUCLightest, 393 kB

mdvirusShortest, 219B

Submit

Login to submit