The winners

Without further ado, the winners and their solutions are:

Chema Cortes with pet1-pych3m4.py:

n=input();d=1;r=""
while d<n:
 d+=1;s=0
 while n%d<1:n/=d;s+=1
 if s:r+=" x %d"%d+"^%d"%s*(s>1)
print r[3:]or n

Javier Mansilla with pet1-jmansilla.py :

s=input();_='';i=1
while s>i:
 c=0;i+=1
 while 1>s%i:c+=1;s/=i
 if c:_+=' x '+`i`+'^%i'%c*(c>1)

Oswaldo Hernández with pet1-hdzos.py:

n=input()
d,f="",1
while n>1:
 f+=1;r=0
 while n%f<1:r+=1;n/=f
 if r:d+=" x %s"%f+"^%s"%r*(r>1)

Special mention

In this opportunity we have considered awarding the "most cheating" award to Darni, that asked us not to rename his file "pet1-darni.py" but use his artistic pseudonym: ZT1pbnB1dCgpCnM9JycKZD0xCndoaWxlIGU+MToKCXA9MDtkKz0xCgl3aGlsZSBlJWQ8MTplLz1kO3ArPTEKCWlmIHA6cys9JyB4ICVkJyVkKyhwPjEpKignXiVkJyVwKQpwcmludCBlKnNbMzpdb3IgZQ==

So this is the content of the file pet1-ZT1pbnB1dCgpCnM9JycKZD0xCndoaWxlIGU+MToKCXA9MDtkKz0xCgl3aGlsZSBlJWQ8MTplLz1kO3ArPTEKCWlmIHA6cys9JyB4ICVkJyVkKyhwPjEpKignXiVkJyVwKQpwcmludCBlKnNbMzpdb3IgZQ==.py:

import base64;exec(base64.decodestring(__file__[5:-3]))

Additional information about the competition can be found at http://python.org.ar/pyar/Proyectos/RevistaPythonComunidad/PET1/Desafio

New challenge

This new challenge was written by Alejandro Santos, who loves problem solving and spent the last week sending several puzzles to the PyAr list.

Thanks to Matías "Tuute" Bellone for his revision of the problem's first draft.

The QQQ number

QQQ is the most popular social network of the Ainohtyp country. Microblogging-style QQQ is a social network where users can only post the word "QQQ". The users can also have other users as contacts, but the other user has to do so too.

The network's administrators built a list with the user sorted by the amount of contact. Curly is at the top of the list with the most contacts.

Your job is to create a program that finds the minimum distance between each user and Curly. That is, the minimum amount of hops between Curly and the rest of the users. If there is more than one way, the shortest is chosen.

For example, lets say Curly is friends with Larry and Moe, Larry is friends with Sue and Sue is friends with Curly. Sue has a distance of 1 with Curly and Larry and Moe have a distance of 1 as well.

It is possible to get from Curly to Sue through Larry, but as Sue is friends with Curly the minimum distance is 1. But if Howard is friends with Moe then the minimum distance from Curly to Howard is 2 as you need to jump through Moe.

Input data

All data must be read through standard input.

Due to privacy concerns the data will be anonymized, you will only get an ID of each user.

The first line will have two numbers: N and M with the amount of users and the amount of friendships in the network respectively.

The users are numbered consecutively, without skipping any user, starting with 1. Curly is number 1. In the following M lines there will be two numbers indicating a relationship between two users.

Some users have no contacts or have no way to build a chain of contacts back to Curly.

Output

You need to print, through standard output N lines with two numbers separated by a single white space. The first number will be the user's id and the second number will be the minimum distance to Curly.

If there is no way to calculate that distance, the second number should be the character "X" instead.

Example

Input:

8 7
1 2
1 3
1 4
2 5
3 5
5 6
4 6
7 8

Output:

1 0
2 1
3 1
4 1
5 2
6 2
7 X
8 X

Participants must send their solution as a .py file named pet2-USERNAME.py (replacing "USERNAME" with a username of your choice) and it will be run with python 2.7 in Alejandro's computer. The winner will be the one to get the solution that passes all specially-crafted tests in the shortest time.

Send your solution to revistapyar@netmanagers.com.ar with DESAFIO2 as the subject of the mail before 2011-July-31.

Good luck and happy brain squshing!

Clarifications and feedback

Any clarifications, if needed, and feedback for participants will be provided through PyAr's wiki at: http://python.org.ar/pyar/Proyectos/RevistaPythonComunidad/PET2/Desafio