5491: 暑期营第六天 store

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定一张图有n个结点和m条边的有向图G,其中第 i 条边从u连向v。对于每一个点,老师想要知道从这个点连出的边的数量(出度)di,以及从这个点连出的每条边的编号。如果从一个点出发有多条边,那么优先输出编号大的边。

Input

第一行包含两个数n,m. 接下来m行,每行包括两个数u,v,表示从u向v连了一条边。其中每条边的编号就是按照输入的顺序,从1 开始编号。

Output

输出包括n行。每行第一个数字di表示从结点连向其他点的边数。接下来有一些数,表示从点 i 连出的每条边的编号。

Sample Input Copy

3 3
1 2
2 3
3 1

Sample Output Copy

1 1
1 2
1 3

HINT

对于20%的数据,满足2≤n≤1000,1≤m≤min(n*( n-1)/2,2000)对于100%的数据,满足2<n≤105,1<m≤min(n*(n-1)/22x105)
再次提醒,如果从一个点出发有多条边,那么优先输出编号大的边。