The ballet master Alexander Ivanovich Pushkin took an interest in him professionally and allowed Nureyev to live with him and his wife. Upon his graduation in 1958, Nureyev joined the Kirov Ballet (now Mariinsky). He moved immediately beyond the corps level, and was given solo roles as a principal dancer from the outset. Nureyev regularly partnered with Natalia Dudinskaya, the company's senior ballerina and wife of its director, Konstantin Sergeyev. Dudinskaya, who was 26 years his senior, first chose him as her partner in the ballet Laurencia. Before long Rudolf Nureyev became one of the Soviet Union's best-known dancers. From 1958 to 1961, in his three years with the Kirov, he danced 15 roles, usually opposite his partner, Ninel Kurgapkina, with whom he was very well paired, although she was almost a decade older than he was. Nureyev and Kurgapkina were invited to dance at a gathering at Khrushchev's dacha, and in 1959 they were allowed to travel outside the Soviet Union, dancing in Vienna at the International Youth Festival. Not long after, he was told by the Ministry of Culture that he would not be allowed to go abroad again. In one memorable incident, Nureyev interrupted a performance of Don Quixote for 40 minutes, insisting on dancing in tights and not in the customary trousers. He relented in the end, but his preferred dress code was adopted in later performances. By the late 1950s, Rudolf Nureyev had become a sensation in the Soviet Union. Yet, as the Kirov Ballet was preparing to go on a tour to Paris and London, Nureyev's rebellious character and non-conformist attitude made him an unlikely candidate for the trip, which the Soviet government considered crucial to its ambitions to demonstrate its "cultural supremacy" over the West. Furthermore, tensions were growing between Nureyev and the Kirov's artistic director Konstantin Sergeyev, who was also the husband of Nureyev's former dance partner Natalia Dudinskaya. After a representative of the French tour organizers saw Nureyev dance in Leningrad in 1960, the French organizers urged Soviet authorities to let him dance in Paris, and he was allowed to go. In Paris, his performances electrified audiences and critics. Oliver Merlin in "Le Monde" wrote,  I will never forget his arrival running across the back of the stage, and his catlike way of holding himself opposite the ramp.