Unique Simple Path

Given an undirected graph \(G=(V,E)\) with \(N\) cities (vertices) and \(M\) bridges (edges), determine whether there exists exactly one simple path between the start city \(s\) and the destination city \(d\). A simple path is one that does not visit any vertex more than once. If there exists exactly one simple path, print UNIQUE; if there are more than one, print MULTIPLE; and if no path exists, print NONE.

The input begins with two integers \(N\) and \(M\). The following \(M\) lines each contain two integers representing a bridge between a pair of cities. The final line contains two integers \(s\) and \(d\) representing the starting and destination cities respectively.

inputFormat

The first line contains two integers \(N\) and \(M\). Each of the next \(M\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le N\)) indicating a bridge between cities \(u\) and \(v\). The last line contains two integers \(s\) and \(d\), the start and destination cities.

outputFormat

Output a single string: UNIQUE if there is exactly one simple path from \(s\) to \(d\), MULTIPLE if there are multiple simple paths, and NONE if no path exists.

4 3
1 2
2 3
3 4
1 4

UNIQUE