Sniffer Installation

The red army has successfully infiltrated the blue army's internal network during an electronic warfare exercise. The blue army has two information centers (servers) and the red army plans to install a sniffer on an intermediate server so that every data packet exchanged between the two centers can be intercepted. However, in the blue army's network there can be multiple paths between the two centers.

Your task is to determine on which intermediate server the sniffer should be installed so that every path from the first information center to the second one passes through that server.

More formally, consider an undirected graph with n nodes numbered from 1 to n where nodes 1 and n represent the two information centers. There are m edges representing the links between servers. You need to find a vertex v (with 1 < v < n) such that if v is removed, there is no path from node 1 to node n. In other words, v is a vertex that lies on every path between node 1 and node n.

In mathematical terms, if we denote by \(P(1,n)\) the set of all paths from node 1 to node n, then the server v you are looking for must satisfy \[ v \in \bigcap_{p \in P(1,n)} p. \]

inputFormat

The first line contains two integers n and m (3 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵) representing the number of servers and the number of connections respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) denoting an undirected edge between server u and server v.

Note that servers 1 and n are the information centers and you are to consider only the intermediate servers (i.e. nodes with id between 2 and n-1) as potential installation points for the sniffer.

outputFormat

Output a single integer representing the ID of the intermediate server at which the sniffer should be installed such that every path from server 1 to server n goes through it. If there is more than one possible server, output the one with the smallest ID. If no such server exists, output -1.

sample

4 3
1 2
2 3
3 4

2