2525
----
               In the year 2525, if man is still alive
                 if woman can survive, they may find

Estonian Air to be the biggest intergallactic carrier servicing
more than 100,000 destinations.  Each week, many different flights 
are offered on discount.  Each flight is only 50,000 euro.  Maarika,
the greatgreatgreatgreatgreatgreatgreatgreatgreatgreatgreatgreat-
greatgreatgreatgreatgreatgreatgreatgreatgreatgreatgreatgranddaughter
of Artjom, wants to travel from Tallinn to Nilatt, the capital of 
New Estonia.  However, she has only saved 100,000 euro.  Hence, she 
can only afford a cheap flight from Tallinn to Nilatt or two cheap 
flights that combined take her from Tallinn to Nilatt.  Every Monday 
morning when the cheap Estonian Air flights are announced on the website 
www.estonian-air.ee, Maarika tries to figure out on a piece of paper 
whether she can travel this week to Nilatt.  Can you help her by 
writing a program that determines whether she can get to Nilatt for
at most 100,000 euro?

Input
-----
Your program will be tested on one or more data sets. The first line 
of each data set will contain two integers C and F.  C (1 <= C <= 100,000)
represents the number of cities that are origin or destination of a cheap 
flight.  F (0 <= F <= 100,000) represents the number of cheap flights.
Following this, there will be F lines, each containing two integers O 
(1 <= O <= 100,000) and D (1 <= D <= 100,000) representing the origin
and destination of a cheap flight.  By convention, 1 is Tallinn
and 2 is Nilatt.  The end of the input will be indicated by a line with 
C = 0 and F = 0.

Output
------
For each data set, your program should print true if Maarika can
travel from Tallinn to Nilatt for at most 100,000 euro, and
false otherwise.

Sample input
------------
6 5
1 2
2 3
3 4
4 5
5 6
6 5
6 5 
5 4
4 3
3 2
2 1
4 5
1 3
3 1
3 2
2 3
3 4
0 0

Sample output
-------------
true
false
true