Pub-lic Good

A bit over three years ago you were elected president of Molvania, a picturesque country that modern dentistry never reached. Winning the election took a few promises, and some of them look exaggerated now.

Molvania's economy is simpler than most. The two main professions are pub owner and beer drinker, and together they account for more than 75 percent of the national product. Beer drinkers borrow money to pay for their beer, and that money becomes income for the pub owners. The pub owners put the income into AAA-rated bonds backed by loans to beer drinkers. Molvanians call the arrangement pub-prime lending.

One of your promises was better city planning. You have picked out a number of construction sites, and each site takes either a pub or the house of a beer drinker. Walkways join some pairs of sites. You want every house to have at least one pub one walkway away, and every pub to have at least one house one walkway away. For some cities no such plan exists, and then you have to say so.

The city has a peculiar layout. Do not assume the walkways can be drawn on a flat map without crossing.

The first line contains two integers $n$ and $m$, the number of construction sites and the number of walkways ($1 \le n \le 10000$, $0 \le m \le 100000$). The sites are numbered 1 to $n$.

Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$), meaning a walkway joins site $x$ and site $y$. No two of these lines are the same.

If no plan puts every pub next to a house and every house next to a pub, print Impossible.

Otherwise print $n$ words separated by single spaces. The $i$-th word is pub or house and says what to build at site $i$.

A city can have many valid plans, so print the one this rule produces. Run a depth-first search over the sites. Go through the sites in increasing order and start a search at every site that is still unvisited; a site where a search starts has depth 0. When the search visits a site, it looks at the neighbors of that site in increasing order of site number and moves into the first neighbor that is still unvisited. A site entered this way gets the depth of the site it came from plus 1. Print pub at every site of even depth and house at every site of odd depth.