Bipartite Organization Problem

You are given a fixed set of 4 members labeled from 1 to 4. Certain pairs of members are provided that must be placed in different groups. In other words, for each given pair (u, v), members u and v must belong to different groups. Your task is to determine if it is possible to split the 4 members into 2 groups such that every given pair has its members in separate groups.

This problem can be modeled as checking whether the undirected graph (with vertices 1, 2, 3, and 4, and edges given by the pairs) is bipartite. If the graph is bipartite, output POSSIBLE; otherwise, output IMPOSSIBLE.

Note: The input is provided through standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

The first line contains a single integer T indicating the number of pairs. Each of the next T lines contains two integers u and v (1 ≤ u, v ≤ 4) separated by a space, representing a pair of members that must be placed in different groups.

outputFormat

Output a single line containing POSSIBLE if it is possible to split the 4 members into 2 groups such that for every given pair, the two members are in different groups. Otherwise, output IMPOSSIBLE.

2
1 4
2 3

POSSIBLE