Випадкова прогулянка

Армія мавп, що підкидають монети (АМПМ), спеціалізується на створенні випадковості. Якісні випадкові числа є важливими для багатьох сфер, таких як криптографія, онлайн-гемблінг, рандомізовані алгоритми та вирішення задач в останні хвилини програмних змагань.

Нещодавно одна з найкращих мавп вийшла на пенсію. Але перед цим вона розробила новий, більш економічний метод генерації випадковості, ніж безпосереднє використання випадковості, створеної мавпами, що підкидають монети. Цей метод починається з вибору неорієнтованого графа з 2^n вузлами, позначеними від $0$ до 2^n - 1. Щоб згенерувати $k$ випадкових $n$-бітних чисел, мавпи підкидають $n$ монет, щоб визначити початковий вузол у графі. Цей номер вузла стає першим числом, що виводиться. Далі мавпи вибирають випадкове ребро з цього вузла і переходять до вузла, з яким це ребро з'єднує. Цей новий вузол стає другим випадковим числом, що виводиться. Потім вони знову вибирають випадкове ребро з цього вузла (можливо, повертаючись до попереднього вузла), переходять по ньому і виводять номер нового вузла. Цей процес триває, поки не буде виведено $k$ чисел.

Під час експериментів АМПМ помітила, що різні графи дають різні розподіли виходу, деякі з яких не дуже випадкові. Тому вони звернулися до вас за допомогою у тестуванні графів, щоб перевірити, чи є випадковість достатньо якісною для продажу.

Граф вважається хорошим, якщо для кожного з $n$ бітів у кожному з $k$ згенерованих чисел ймовірність того, що цей біт буде $1$, перевищує $25\%$ і менша за $75\%$.