낯선 사람들의 그룹

최근 여러 번의 합병으로 생긴 소프트웨어 회사는 서로 다른 도시에 몇 개의 사무실을 두고 있다. 각 사무실에는 그곳에서 일하는 모든 직원을 아는 인사 담당자가 한 명씩 있다. 그 밖에도 많은 직원이 서로 알고 지내며, 그중에는 다른 사무실의 직원도 있다. 아는 관계는 대칭이다. 직원 $a$가 직원 $b$를 알면 $b$도 $a$를 안다. 모든 직원은 (바람직하게도) CEO를 알고 있지만, CEO가 모든 직원을 아는 것은 아니다. CEO는 모든 인사 담당자를 알지만, 그 밖의 직원은 많이 알지 못한다. 이 상황은 바뀌어야 한다!

인사 담당자 한 명이 직원들이 서로를 더 잘 알도록 회사 야유회를 계획하라는 지시를 받았다. 전체 직원이 묵을 수 있는 호텔은 없다. 이를 장점으로 바꿀 수 있을까? 그는 서로 가까운 호텔을 최대 3곳 이용하면, 직원들을 호텔마다 한 그룹씩 세 그룹으로 나눌 수 있고, 같은 그룹 안에서 이미 서로 아는 직원이 없도록 만들 수 있다고 생각한다. 그렇게 하면 새로운 만남이 생기기 쉬울 것이다.

계획의 초기 단계라서 그는 그룹의 크기에는 관심이 없다. 이런 나눔이 가능한지만 알고 싶어 한다. 그는 서로 아는 직원 쌍의 전체 목록을 제공한다. 인사 담당자와 CEO가 누구인지는 알려주지 않는다. 다만 CEO가 아는 직원은 (인사 담당자를 포함해) 최대 $15$명이고, 회사는 최대 $8$개의 사무실에 나뉘어 있다는 사실은 알고 있다.

첫 줄에 직원 수와 서로 아는 직원 쌍의 수를 나타내는 정수 $N$과 $M$이 주어진다 ($2 \leq N \leq 1000, 1 \leq M \leq 100000$). 이어서 $M$개의 줄에 각각 정수 $a$와 $b$가 주어지며 ($1\leq a\neq b \leq N$), 이는 직원 $a$가 직원 $b$를 안다는 뜻이다.

주어지는 모든 테스트 케이스에는 위에서 설명한 대로 인사 담당자와 CEO를 포함해 직원을 사무실에 나누는 방법이 적어도 하나 있다. 정리하면, CEO는 다른 사람을 최대 $15$명 아는 직원이다. 나머지 직원은 최대 $8$개의 사무실로 나뉘며, 각 사무실에는 그 사무실의 다른 모든 직원을 아는 직원(인사 담당자)이 한 명 있다. CEO는 모든 인사 담당자도 안다. 서로 다른 사무실의 직원끼리 서로 알 수도 있다.

서로 아는 직원들이 같은 그룹에 속하지 않도록 직원을 최대 세 그룹으로 나눌 수 있으면, 입력에서의 번호 순서대로 각 직원의 그룹 번호 $1$, $2$, $3$을 한 줄에 출력한다. 그룹 번호 사이는 공백 한 칸으로 구분한다. 해가 여러 개라면 그중 아무거나 출력해도 된다. 그런 나눔이 없으면 Impossible을 출력한다.