#include <iostream>
#include <queue>
#include <vector>
using number = unsigned long int;
struct node {
const number parent;
const number left;
const number right;
bool infected;
node(number parent, number left, number right) : parent(parent), left(left), right(right), infected(false) {}
};
struct entry {
const number node_number;
const number step;
entry(number node_number, number step) : node_number(node_number), step(step) {}
};
std::ostream& operator<<(std::ostream& os, const entry& e) {
os << "node " << e.node_number << " is infect at minute " << e.step;
return os;
};
int main(void) {
// 対象となる二分木。
// 各要素はそれに接続されている親ノード、左の子、右の子の番号を持つ。
// 0 は終端を表している。
std::vector<node> tree = {
{0, 0, 0}, // 0 番目ノードは使わないので適当に埋める
{0, 5, 3}, // 1 番目ノード
{4, 0, 0}, // 2 番目ノード
{1, 10, 6}, // 3 番目ノード
{5, 9, 2}, // 4 番目ノード
{1, 0, 4}, // 5 番目ノード
{3, 0, 0}, // 6 番目ノード
{0, 0, 0}, // 7 番目ノードは使わないので適当に埋める
{0, 0, 0}, // 8 番目ノードは使わないので適当に埋める
{4, 0, 0}, // 9 番目ノード
{3, 0, 0}, // 10 番目ノード
};
// 最初の予定としてスタート地点を入れる
std::queue<entry> schedule;
schedule.emplace(3, 0);
schedule.emplace(5, 0);
while (! schedule.empty()) {
auto task = schedule.front();
schedule.pop();
if (auto& cursor = tree.at(task.node_number); cursor.infected == false) {
std::cout << task << std::endl;
cursor.infected = true;
if (cursor.parent) schedule.emplace(cursor.parent, task.step + 1);
if (cursor.left) schedule.emplace(cursor.left, task.step + 1);
if (cursor.right) schedule.emplace(cursor.right, task.step + 1);
}
}
};