Can I go there?

At one point, there was a president who traveled around Japan to do business. One day he got a mysterious ticket. If you use the ticket, the train fare will be free regardless of the distance to the destination. However, when moving from the current station to the adjacent station is counted as one step, if the number of steps to move is not exactly equal to the number written on the ticket, an additional fee will be charged. It is forbidden to move around a section immediately, but it is permissible to go through a station or section that you have already visited multiple times. For example, you cannot move to station 1, station 2, or station 1, but there is no problem with moving to station 1, station 2, station 3, station 1, or station 2. Also, if you finally arrive at your destination, you may go through the starting point and destination as many times as you like.

The president immediately decided to use this ticket to go to his next destination. However, since the route map is complicated, the route cannot be easily determined. Your job is to write a program on behalf of the president to determine if you can reach your destination for free.

Stations are numbered from 1 to N, with the departure station being 1 and the destination station being N. The route map is given by the row of sections connecting the two stations. The section can pass in either direction. It is guaranteed that there is no section connecting the same stations and that there is at most one section connecting a pair of stations.

Input

The input consists of multiple datasets.

Each dataset is given in the following format.

N M Z s1 d1 s2 d2 ... sM dM

N is the total number of stations, M is the total number of sections, and Z is the number of steps written on the ticket. si and di (1 ≤ i ≤ M) are integers representing station numbers, indicating that there is an interval between station si and station di, respectively.

N, M, Z are positive integers and satisfy the following conditions: 2 ≤ N ≤ 50, 1 ≤ M ≤ 50, 0 <Z <231.

After the last dataset, there is a line that says "0 0 0".

The number of datasets does not exceed 30.

Output

For each dataset, output a one-line string containing only " yes "if the destination can be reached with just the number of steps written on the ticket, or" no" if not. ..

Example

Input

2 1 1 1 2 2 1 2 1 2 3 1 2 1 2 8 8 5778 1 2 2 3 2 4 3 5 5 6 6 7 7 8 4 8 8 8 5777 1 2 2 3 2 4 3 5 5 6 6 7 7 8 4 8 0 0 0

Output

yes no no yes no

inputFormat

Input

The input consists of multiple datasets.

Each dataset is given in the following format.

N M Z s1 d1 s2 d2 ... sM dM

N is the total number of stations, M is the total number of sections, and Z is the number of steps written on the ticket. si and di (1 ≤ i ≤ M) are integers representing station numbers, indicating that there is an interval between station si and station di, respectively.

N, M, Z are positive integers and satisfy the following conditions: 2 ≤ N ≤ 50, 1 ≤ M ≤ 50, 0 <Z <231.

After the last dataset, there is a line that says "0 0 0".

The number of datasets does not exceed 30.

outputFormat

Output

For each dataset, output a one-line string containing only " yes "if the destination can be reached with just the number of steps written on the ticket, or" no" if not. ..

Example

Input

2 1 1 1 2 2 1 2 1 2 3 1 2 1 2 8 8 5778 1 2 2 3 2 4 3 5 5 6 6 7 7 8 4 8 8 8 5777 1 2 2 3 2 4 3 5 5 6 6 7 7 8 4 8 0 0 0

Output

yes no no yes no

样例

2 1 1
1 2
2 1 2
1 2
3 1 2
1 2
8 8 5778
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
8 8 5777
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
0 0 0

yes
no
no
yes
no

</p>