分队问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

每年的GDOI在比赛结束后都会组织选手参加一次游玩活动。由于人数众多,通常把选手分成两队出发。组委会为了创造机会让选手们互相认识,他们想尽量把原来相互间比较熟悉的选手们分在不同的队,让每位选手有更多的机会接触其他原来不认识的选手。因为参赛的名额有限,选手们参赛的机会不多,基本上可以假定每位选手最多只和其他3名选手比较熟悉。而组委会希望在每支游玩的队伍中,每位选手最多只熟悉另一名选手。现在给出选手之间的关系,想请你给出个分配方案。

Input

第1行只有两个正整数n(n<=1000)和m。n表示选手总数,选手从1到n编号;m表示有m对相互熟悉的选手。接下有m行,每行有两个正整数a和b,表示a和b比较熟悉。两个数之间有一个空格隔开。

Output

共有两行,分别描述两支队的人员组成情况。
每行第1个数k为该队的人数,接下来k个数表示组成这支队的选手编号,每个数之间用一个空格隔开。

Sample Input

1 0

Sample Output

1 1
0

Hint

 

Source