/
1282E.go
107 lines (99 loc) · 1.79 KB
/
1282E.go
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package main
import (
"bufio"
. "fmt"
"io"
"sort"
)
// github.com/EndlessCheng/codeforces-go
func CF1282E(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
type pr struct{ x, y int }
sort3 := func(a ...int) (x, y, z int) { sort.Ints(a); return a[0], a[1], a[2] }
var T, n, x, y, z int
for Fscan(in, &T); T > 0; T-- {
Fscan(in, &n)
id := make([]map[pr]int, n)
for i := range id {
id[i] = map[pr]int{}
}
cnt := make([]int, n)
for i := 1; i < n-1; i++ {
Fscan(in, &x, &y, &z)
x, y, z = sort3(x-1, y-1, z-1)
id[x][pr{y, z}] = i
id[y][pr{x, z}] = i
id[z][pr{x, y}] = i
cnt[x]++
cnt[y]++
cnt[z]++
}
if n == 3 {
Fprintln(out, 1, 2, 3)
Fprintln(out, 1)
continue
}
ans := make([]int, 0, n-2)
g := make([][]int, n)
inner := map[pr]bool{}
add := func(v, w int) {
if v > w {
v, w = w, v
}
if !inner[pr{v, w}] {
g[v] = append(g[v], w)
g[w] = append(g[w], v)
}
}
q := []int{}
for i, c := range cnt {
if c == 1 {
q = append(q, i)
}
}
for n -= 2; n > 0; n-- {
x := q[0]
q = q[1:]
p, i := pr{}, 0
for p, i = range id[x] {
break
}
ans = append(ans, i)
y, z := p.x, p.y
if cnt[y]--; cnt[y] == 1 {
q = append(q, y)
}
if cnt[z]--; cnt[z] == 1 {
q = append(q, z)
}
add(x, y)
add(x, z)
inner[p] = true
x, y, z = sort3(x, y, z)
delete(id[x], pr{y, z})
delete(id[y], pr{x, z})
delete(id[z], pr{x, y})
}
fa, v := -1, 0
for {
Fprint(out, v+1, " ")
for _, w := range g[v] {
if w != fa {
fa, v = v, w
break
}
}
if v == 0 {
break
}
}
Fprintln(out)
for _, v := range ans {
Fprint(out, v, " ")
}
Fprintln(out)
}
}
//func main() { CF1282E(os.Stdin, os.Stdout) }