# 明明都是我先來的...
https://neoj.sprout.tw/problem/752/
> 是我，是我先，明明都是我先來的...... -- [冬馬和紗](https://zh.moegirl.org.cn/%E5%86%AC%E9%A9%AC%E5%92%8C%E7%BA%B1) (@[白色相簿2](https://zh.moegirl.org.cn/%E7%99%BD%E8%89%B2%E7%9B%B8%E7%B0%BF2))

> 白色相簿什麼的已經無所謂了。因為已經不再有歌，值得去唱了。傳達不了的戀情已經不需要了。因為已經不再有人，值得去愛了。
ホワイトアルバムなんて知らない。だって、もう何も歌えない。届かない恋なんてしない。だって、もう人を愛せない。
[name=《白色相簿2》終章官方宣傳詞][color=lightblue]

> 為什麼你會這麼熟練啊！你和雪菜親過多少次了啊！？你到底要把我甩開多遠你才甘心啊！？
なんでそんなに慣れてんだよっ！雪菜と…何回キスしたんだよ！？どこまであたしを置いてきぼりにすれば気が済むんだよ！？
[name=冬馬和紗, 第11話][color=lightblue]

> 是我，是我先，明明都是我先來的……接吻也好，擁抱也好，還是喜歡上那傢伙也好。
あたしが、先だった……先だったんだ……キスしたのも、抱き合ったのも。そいつのこと好きになったのも。
[name=冬馬和紗][color=lightblue]

> 為什麼會變成這樣呢……第一次有了喜歡的人。有了能做一輩子朋友的人。兩件快樂事情重合在一起。而這兩份快樂，又給我帶來更多的快樂。得到的，本該是像夢境一般幸福的時間……但是，為什麼，會變成這樣呢……
どうしてこうなるんだろう…初めて、好きな人が出来た。一生ものの友だちができた。嬉しいことが二つ重なって。その二つの嬉しさが、また、たくさんの嬉しさを連れてきてくれて。夢のように幸せな時間を手に入れたはずなのに…なのに、どうして、こうなっちゃうんだろう…
[name=小木曾雪菜][color=lightblue]

### 輸入格式
+ 第一行兩個整數N, M，分別代表著有N個人(編號從0 ~ N-1)以及M對喜歡關係。

+ 其中這個M對是按照時間順序所排列的，保證一個人不會重複喜歡同個人，也不會喜歡自己。但是有可能他會同時喜歡很多人。
+ 接下來M行，每行有兩個數字，分別代表著被喜歡的人以及喜歡的人。

### 輸出格式
+ 請輸出N行，每行內輸出他們的編號，之後依序輸出到底有誰喜歡這個人。 (需要按照時間排列)
+ 例如現在2, 3, 4喜歡1，那麼當輸出到1這個人的時候會長得像這樣1: 2 3 4這樣。注意，每行不能有結尾空格。
+ 如果這個人很可憐，沒有人愛他，那就不要在鞭屍他了。這種情況不要為他輸出東西。(以範例測資的話，0這個人沒人愛，就不要輸出他。)
### 提示
+ 這題最基礎的作法是直接開一個NxN的二維陣列，然後每看到一組(a,b)，就把b放到第a列當前的最後一個。例如假設現在有(1, 2), (2, 3), (1, 4)的組合，二維陣列可能會像這樣:

+ ary[1] 有兩個數字: 2, 4
+ ary[2] 有一個數字: 3
+ 而因為可能所有人都同時喜歡同一個人，所以陣列的第二維度宣告可能要開到最大，即為N。
+ 但如果當N太大，你就無法開成這樣(因為沒有那麼多的空間)。所以我們會用神奇的方法存下來。這個神奇的方法我們已經幫妳寫好了，你能看懂並利用它嗎?

+ 你不需要寫出整份程式，你只需要實作print函數。你的程式會在附圖code上插入:

#include <iostream>
#include <cassert>
#define MAXN 100000
#define MAXM 1000000
using namespace std;
typedef struct person{
    int count;
    int *loved_begin;
}person;
int storage[MAXM];
person all_people[MAXN];
int pairs[MAXM][2];
int now_cnt[MAXN] = {0};
void prepare(int n, int m, person *all_people, int *storage){
    // input
    for(int i=0; i<m; i++)
        cin >> pairs[i][0] >> pairs[i][1];
    
    // initialization 
    for(int i=0; i<n; i++)
        all_people[i].count = 0;
    
    // calculate_count
    for(int i=0; i<m; i++)
        all_people[pairs[i][0]].count++;
​
    // calculate start
    int now_start = 0;
    for(int i=0; i<n; i++){
        all_people[i].loved_begin = storage+now_start;
        now_start += all_people[i].count;
    }
​
    // push element into storage
    for(int i=0; i<m; i++){
        int be_loved = pairs[i][0], to_love = pairs[i][1];
        int now_filled_position = now_cnt[be_loved];
        person be_loved_person = all_people[be_loved];
        (be_loved_person.loved_begin)[now_filled_position] = to_love;
        // next position move to next
        now_cnt[be_loved]++;
    }
​
    // destroy the elements
    for(int i=0; i<m; i++)
        pairs[i][0] = pairs[i][1] = 0;
​
}
void print(int, int, person *, int *);
int main(){
    int n, m;
    cin >> n >> m;
    prepare(n, m, all_people, storage);
    print(n, m, all_people, storage);
    return 0;
}

#include "main.cpp"
/*
    你的code會被放在這裡。
*/

### 輸入限制
+ $0 < N < 10^5$

+ $0 < M < 10^6$

+ 接下來M個配對的所有數字都會介於0 ~ N-1之間。

### 範例輸入

4 5
1 2 
2 3 
1 3 
3 1
2 0

### 範例輸出

1: 2 3
2: 3 0
3: 1

# Code

void print(int n, int m, person *all_people, int *storage){

  for (int i = 0; i < n; i++)
  {
    if (all_people[i].count == 0)
      continue;
    cout << i << ":";

    person be_loved_person = all_people[i];

    for (int j = 0; j < all_people[i].count; j++)
      cout << " " << be_loved_person.loved_begin[j];
    cout << "\n";
  }
}