1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

struct arc { int v, c; };

vector<vector<arc>> e, ee;
vector<int> seq, pre, post, par, semi, label, idom;

void dfs(int u) {
  pre[u] = seq.size();
  seq.push_back(u);
  for (arc a: e[u])
    if (par[a.v] == -1) {
      par[a.v] = u;
      dfs(a.v);
    }
  post[u] = seq.size();
}

int eval(int v, int last) {
  if (par[v] == -2 || pre[par[v]] < last)
    return v;
  int u = eval(par[v], last);
  par[v] = u;
  if (pre[label[u]] < pre[label[v]])
    label[v] = label[u];
  return v;
}

bool semiNca(int n, int r) {
  par.assign(n, -1);
  par[r] = -2; 
  idom.resize(n);
  idom[r] = -1;
  pre.resize(n);
  post.resize(n);
  dfs(r);
  semi.resize(n);
  label.resize(n);
  idom.resize(n);
  REP(i, n) {
    label[i] = semi[i] = i;
    idom[i] = par[i];
    if (par[i] == -1)
      return false;
  }
  for (size_t i = seq.size() - 1; i; i--) {
    int v = seq[i];
    for (arc &a: ee[v]) {
      int w = label[eval(a.v, i+1)];
      if (pre[w] < pre[semi[v]])
        semi[v] = w;
    }
    label[v] = semi[v];
  }
  for (size_t i = 1; i < seq.size(); i++) {
    int v = seq[i];
    while (pre[idom[v]] > pre[semi[v]])
      idom[v] = idom[idom[v]];
  }
  return true;
}

int main() {
  int n, i, j, c;
  cin >> n;
  e.resize(n);
  ee.resize(n);
  while (cin >> i >> j) {
    e[i].push_back(arc{j, 0});
    ee[j].push_back(arc{i, 0});
  }
  if (!semiNca(n, 0))
    return 0;
  REP(i, n)
    printf("%d: %d\n", i, idom[i]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

digraph {
  0 -> 1
  1 -> 2
  2 -> 3
  1 -> 4
  4 -> 5
  3 -> 6
  3 -> 5
  2 -> 0
  3 -> 1
  0 -> 6
  6 -> 4
  5 -> 6
  3 -> 1
  5 -> 2
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

digraph {
  0 -> 1
  0 -> 2
  2 -> 3
  3 -> 4
  2 -> 5
  5 -> 6
  4 -> 7
  7 -> 8
  3 -> 9
  3 -> 4
  3 -> 7
  8 -> 2
  5 -> 2
  1 -> 8
  8 -> 6
  6 -> 4
  1 -> 9
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

digraph {
  0 -> 1
  1 -> 2
  0 -> 3
  1 -> 4
  1 -> 5
  4 -> 6
  2 -> 7
  5 -> 8
  3 -> 9
  4 -> 8
  6 -> 4
  6 -> 5
  5 -> 3
  5 -> 4
  6 -> 3
  3 -> 4
  2 -> 5
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <cstdio>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

struct arc { int v, c; };
vector<vector<arc>> e, ee;
vector<int> seq, pre, post, idom;
int dfn;

void dfs(int u) {
  pre[u] = dfn++;
  for (arc a: e[u])
    if (idom[a.v] == -1) {
      idom[a.v] = u;
      dfs(a.v);
    }
  seq.push_back(u);
  post[u] = dfn;
}

void idfs(int n, int r) {
  bool changed;
  pre.resize(n);
  post.resize(n);
  seq.clear();
  idom.assign(n, -1);
  idom[r] = -2;
  dfn = 0;
  dfs(r);
  do {
    changed = false;
    for (int i = seq.size() - 2; i >= 0; i--) {
      int v = seq[i], x = -1;
      for (arc &a: ee[v]) {
        if (x == -1)
          x = a.v;
        else {
          int y = a.v;
          while (x != y) {
            if (pre[x] > pre[y])
              x = idom[x];
            else
              y = idom[y];
          }
        }
      }
      if (x != idom[v]) {
        idom[v] = x;
        changed = true;
      }
    }
  } while (changed);
}

int main() {
  int n, i, j, c;
  cin >> n;
  e.resize(n);
  ee.resize(n);
  while (cin >> i >> j) {
    e[i].push_back(arc{j});
    ee[j].push_back(arc{i});
  }

  idfs(n, 0);
  REP(i, n)
    printf("%d: %d\n", i, idom[i]);
}