Еще на первом курсе сдал эту задачу без всякого потока. Я тогда его, просто-напросто, не знал :) Эта задача с одного из отборочных туров всесибирской олимпиады какого-то две дысячи мохнатого года. Если перевести на язык графов, то я сначала удалял висячие вершины, а потом подсчитывал степени вершин в каждой из компонент связности. По этим степеням ответ уже определялся однозначно. Более детальное решение вспоминать лень, но общую идею я вроде вспомнил :)