#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;


int parnt[] = { -1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3 };
int level[13] = { 0 };


int getLevel(int cur)
{
	if (level[cur] != -1)
		return level[cur];
	if (parnt[cur] == -1)
	{
		level[cur] = 1;
		return 1;
	}
	level[cur] = getLevel(parnt[cur]) + 1;
	return level[cur];
}


struct edge
{
	int a, b, cost;
	edge(int a = 0, int b = 0, int cost = 0) :a(a), b(b), cost(cost){};
};



edge arr[13];

struct node
{
	int value;
	node* next;
	node(int vl) :value(vl){};
};

class stack
{
	node* head;

public:
	stack()
	{
		head = 0;
	}
	int top()
	{
		if (head == 0)
			return -999999999;
		return head->value;
	}
	bool isEmpty()
	{
		return head == 0;
	}
	void push(int vl)
	{
		node* newElem = new node(vl);
		newElem->next = head;
		head = newElem;
	}
	void pop()
	{
		if (head == 0)
			return;
		node* tmp = head;
		head = head->next;
		delete tmp;
	}

	void deleteNodeByVal(int vl)
	{
		node* cNode = head;
		while (cNode != 0)
		{
			if (cNode->value == vl)
			{
				node* tmp = cNode;
				cNode = cNode->next;
				delete tmp;
				continue;
			}
			else
			{
				cNode = cNode->next;
			}
		}
	}

};



class PuchkiDug
{
private:

	int* heads;
	int* links;
	edge* edges_p;

	int n;
	int m;

public:
	PuchkiDug(edge* allEdges, int n, int m) : n(n), m(m)
	{
		edges_p = allEdges;
		heads = new int[n];
		links = new int[m];

		memset(heads, -1, sizeof(int)* n);
		memset(links, -1, sizeof(int)* m);

		for (int i = 0; i < m; ++i)
		{
			links[i] = heads[edges_p[i].a];
			heads[edges_p[i].a] = i;
		}
	}

	void printData()
	{
		for (int i = 0; i < n; ++i)
		{
			int cr = heads[i];
			while (cr != -1)
			{
				cout << edges_p[cr].b << " ";
				cr = links[cr];
			}
			cout << endl;
		}
	}

	void getParentTree(int* outp, int start)
	{
		memset(outp, -1, sizeof(int)* n);


		queue<int> que;
		que.push(start);
		outp[start] = -2;
		while (!que.empty())
		{
			int cr = que.front();
			que.pop();

			int hd = heads[cr];

			while (hd != -1)
			{
				int to = edges_p[hd].b;
				if (outp[to] == -1)
				{
					outp[to] = cr;
					que.push(to);
				}
				hd = links[hd];
			}
		}
	}


	void djicstra(int* distances, edge* edges, int vCount, int eCount, int start)
	{
		int maxEdge = 0;
		for (int i = 0; i < eCount; ++i)
		{
			maxEdge = max(maxEdge, edges[i].cost);
		}

		stack* cherpack = new stack[maxEdge];
		distances[start] = 0;
		bool isWorking = true;
		cherpack[0].push(start);
		while (isWorking)
		{
			isWorking = false;
			for (int i = 0; i < maxEdge; ++i)
			{
				if (cherpack[i].isEmpty())
					continue;

				int cVert = cherpack[i].top();
				cherpack[i].pop();
				int dist = distances[cVert];

				int cEdge = heads[cVert];
				while (cEdge != -1)
				{
					int nx = edges[cEdge].b;
					int cost = edges[cEdge].cost;
					if (distances[nx] > distances[cVert] + cost)
					{
						int cherp = distances[nx] % maxEdge;
						distances[nx] = distances[cVert] + cost;
						cherpack[cherp].deleteNodeByVal(nx);
						cherp = distances[nx] % maxEdge;
						cherpack[cherp].push(nx);
						isWorking = true;
					}
					cEdge = links[cEdge];
				}


			}

		}


	}

};






int main()
{
	memset(level, -1, sizeof(int)* 13);
	arr[0] = edge(0, 1, 2);
	arr[1] = edge(0, 2, 4);
	arr[2] = edge(0, 3, 1);

	arr[3] = edge(1, 4, 20);
	arr[4] = edge(1, 5, 30);
	arr[5] = edge(1, 6, 13);

	arr[6] = edge(2, 7, 12);
	arr[7] = edge(2, 8, 23);
	arr[8] = edge(2, 9, 41);

	arr[9] = edge(3, 10, 51);
	arr[10] = edge(3, 11, 53);
	arr[11] = edge(3, 12, 93);
	arr[12] = edge(3, 0, 85);

	PuchkiDug puch(arr, 13, 13);

	cout << getLevel(5) << endl;
	/*int dstts[13] = { 0 };
	for (int i = 0; i < 13; ++i)
		dstts[i] = 999999999;

	puch.djicstra(dstts, arr, 13, 13, 3);

	puch.printData();
	int par[13] = { 0 };
	puch.getParentTree(par, 3);
	for (int i = 0; i < 13; ++i)
		cout << par[i] << " ";*/

}